# 三角形最小路径和

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        result = list()
        for layer in triangle:
            if not result:
                result.append(layer[0])
                continue
            length = len(result)
            for i in range(len(layer)):
                if i == 0:
                    result.append(layer[i]+result[i])
                    continue
                if i == len(layer)-1:
                    result.append(layer[i]+result[i-1])
                    continue
                minnum = min(result[i-1], result[i])
                result.append(minnum + layer[i])
            for _ in range(length):
                result.pop(0)
        return min(result)
